Digital video is typically embodied as a collection of digital still frames that convey motion when displayed in succession. Because visual information (such as digital video) naturally consumes large amounts of data, data compression is often applied to reduce the amount of data without substantially degrading the original imagery. Motion estimation is a compression technique that is most often applied to digital video.
According to the motion estimation approach, a first frame is broken down into small pieces (referred to as “macro blocks”); then, each macro block is searched for in a data field (referred to as a “search window”) of a second frame that follows or precedes the first frame (in the sequence of frames that the video information is comprised of). The macro block being searched for may be referred to as a “reference macro block” or a “reference block”. For each found reference macro block (ideally all reference macro blocks are found in the second frame), a displacement vector is recorded that describes the movement of the reference macro block. Thus, compression is achieved by preserving displacement vectors instead of actual visual content.
FIG. 1 demonstrates a simple example of motion estimation for a digital video that depicts an automobile moving from left to right. A “current” frame 103 corresponds to the first frame referred to above. The current frame 103 follows a “previous” frame 101 in the sequence of frames that convey movement of the automobile from left to right in FIG. 1. The previous frame 101 corresponds to the second frame referred to just above. A reference macro block 102b that captures the nose of the automobile is depicted in the current frame 103 and a search window 104 is depicted in the previous frame 101.
It is important to point out that other scenarios are possible as between which frame is the “first” frame having the reference block and which frame is the “second” frame having the search window. For example, alternatively, the second frame may be a subsequent frame relative to the first frame (rather than a previous frame as described just above with respect to FIG. 1).
Note that other reference macro blocks would be defined in current frame 103. Notably, the sequence of the previous and current frames 101, 103 portray the automobile moving a distance K to the right. According to basic motion estimation, a field of data 104 larger than a macro block is taken from the previous frame 101 and used as a search window for finding the reference macro block 102b of the current frame 103. The search window 104 may be centered around the center position of the current frame's reference macro block 102b (i.e., the search window 104 is centered at a horizontal offset of K from the frame origin in the example of FIG. 1). An aptly size search window 104 should always result in the finding of the reference macro block 102b (if the object undergoing movement does not change its own features). According to the example of FIG. 1, the reference macro block 102b of the current frame 103 is discovered in the search window 104 a distance K to the left of its original position within the current frame 101. As such, a displacement vector of (K,0) is recorded for macro block 102a (i.e., ((xc−xp),(yc−yp))=((K−0),(0−0)=(K,0); where, “c” denotes “current” and “p” denotes previous).